package com.fw.leetcode.greedy;

import com.fw.leetcode.LeetCode;

/**
 * 409. Longest Palindrome
 *
 * Given a string s which consists of lowercase or uppercase letters, return the length of the longest
 * palindrome that can be built with those letters.
 *
 * Letters are case sensitive, for example, "Aa" is not considered a palindrome.
 *
 * Example 1:
 *  Input: s = "abccccdd"
 *  Output: 7
 *  Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7.
 *
 * Example 2:
 *  Input: s = "a"
 *  Output: 1
 *  Explanation: The longest palindrome that can be built is "a", whose length is 1.
 *
 * Constraints:
 *  1 <= s.length <= 2000
 *  s consists of lowercase and/or uppercase English letters only.
 */
public class Num_0409 implements LeetCode {

    private interface Solution {
        int longestPalindrome(String s);

        default void assertExpected(String s, int expected) {
            if (longestPalindrome(s) != expected) {
                longestPalindrome(s);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public int longestPalindrome(String s) { // 最长回文串 集合标记 偶数奇数字符统计：时O(n) 空O(m)
            // 定义128个ASCII码数组，映射字符统计
            int[] set = new int[128];
            // 遍历统计各字符出现个数
            for (int i = 0; i < s.length(); i++) {
                set[s.charAt(i)]++;
            }
            // 回文计数
            int result = 0;
            for (int i = 0; i < set.length; i++) {
                if (set[i] != 0) {
                    result += set[i] / 2 * 2; // >2 的能构成成双组合
                    if (set[i] % 2 == 1 && result % 2 == 0) { // 奇数的能构成中间（任意），但整个回文串只需一个奇数字符
                        result++;
                    }
                }
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected("abccccdd", 7); // dccaccd => 4c 2d 1a
        solution.assertExpected("a", 1); // a
    }
}
